package pers.vic.basics.sort;

/**
 * @description:插入排序
 * @author Vic.xu
 * @date: 2020/10/15 0015 14:57
 */
public class InsertionSort {
    /*
    排序思路：一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表
     外层循环对除了第一个元素之外的所有元素，
     内层循环对当前元素前面有序表进行待插入位置查找，
     */

    public static void sort(int[] arr) {
        int len = arr.length;

        //从第2位开始，分别在左侧已经排好的数组中找到合适的位置
        for (int i = 1; i < len; i++) {
            int temp = arr[i];
            int j = i;
            //左侧的数据大于当前值则后移
            while (j > 0 && arr[j-1] > temp) {
                arr[j] = arr[j-1];
                j--;
            }
            //把当前数值放入空出来的位置
            arr[j] = temp;

        }

    }
}
